package com.lili.math;

/**
 * @Auther: 李 力
 * @Date: 2024/8/2
 * @Description: 数字的补数
 * @version: 1.0
 */
public class LeetCode476 {
    /*
     *  时间复杂度: O(n)
     *  空间复杂度: O(n)
     */
    public static int findComplement1(int num) {
        String binaryString = Integer.toBinaryString(num);
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < binaryString.length(); i++) {
            char c = binaryString.charAt(i);
            c = c == '0' ? '1' : '0';
            builder.append(c);
        }
        binaryString = builder.toString();
        return Integer.parseInt(binaryString, 2);
    }


    /*
     * 时间复杂度: O(lognum)
     * 空间复杂度: O(1)
     */
    public static int findComplement2(int num) {
        int bit = 0;
        for (int i = 1; i <= 30; i++) {
            if (num >= 1 << i) {
                bit = i;
            } else {
                break;
            }
        }
        int mask = bit == 30 ? 0x7fffffff : (1 << (bit + 1)) - 1;
        return num ^ mask;
    }

}
